//
//  ProblemOffer51.swift
//  TestProject
//
//  Created by 武侠 on 2021/7/22.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 51. 数组中的逆序对
 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

 示例 1:
     输入: [7,5,6,4]
     输出: 5
 限制：
    0 <= 数组长度 <= 50000
 */
@objcMembers class ProblemOffer51: NSObject {
    func solution() {
        print(reversePairs([7,5,6,4]))
    }
    
    
    /*
     方法一：2层遍历
     创建一个数组list，存储：从nums后面进行排序的序列：组成一个降序的序列
     例如：[], 4=>[4], 6=>[6,4], 5=>[6,5,4], 7=>[7,6,5,4]
     其实就是求：在list中有几个比nums[i]小的值
     */
    func reversePairs(_ nums: [Int]) -> Int {
        if nums.count <= 1 {
            return 0
        }
        
        var n = 0
        var list:[Int] = [nums.last!]
        for value in (0..<nums.count-1).reversed() {
            if nums[value] <= list.last! {
                list.append(nums[value])
            } else {
                for i in (0..<list.count) {
                    if nums[value] > list[i] {
                        n +=  list.count - i
                        list.insert(nums[value], at: i)
                        break
                    }
                }
            }
        }
        return n
    }
    
    /*
     方法二：归并排序
     归并排序分为两个步骤：分和治
     分：将数组从中间开发分成2个子数组，然后递归直到分成长度是2 或者 1 的数组，
     如果是长度2的话，进行排序，并计算是“逆序对”的个数
       [7,5,6,4]
     [7,5]   [6,4]  排序，这2个数组都是“逆序对”的，所以n = 2
     [5,7]   [4,6]
     治：合并相邻的2个数组，因为都是已经排好序的数组，所以很好排序
     
     这里可以在治这一阶段来求我们需要的“逆序对”，例如：[5,7]   [4,6]
     遍历左边的数组时：left[i]，找到右边数组中比left[i]小的个数就是我们的“逆序对”个数
     例如：
     left[i] = 5, 右边有一个比5小的有1个 => n+=1 => n=3
     left[i] = 7, 右边有一个比7小的有2个 => n+=2 => n=5
     */
    func reversePairs2(_ nums: [Int]) -> Int {
        if nums.count <= 1 {
            return 0
        }
        
        var list = nums
        return merge_sort(&list, 0, nums.count-1)
    }
    
    func merge_sort(_ nums: inout [Int], _ left: Int, _ right: Int) -> Int {
        if left >= right {
            return 0
        }
        let mid = (left + right) >> 1
        
        var n = merge_sort(&nums, left, mid) + merge_sort(&nums, mid+1, right)
        let temp = nums[left...right]
        print("n=", n, "left=", left, "right=", right, "mid=", mid, temp)
        var k = left, i = left, l = mid+1
        
        // 未完成
        while i <= mid || l <= right {
            if i <= mid, l <= right {
                if temp[i] > temp[l] {
                    nums[k] = temp[l]
                    l += 1
                    n += mid - i + 1            // 统计个数
                } else if temp[i] == temp[l] {
                    nums[k] = temp[l]
                    l += 1
                } else {
                    nums[k] = temp[i]
                    i += 1
                }
            } else if i <= mid {
                nums[k] = temp[i]
                i += 1
                n += right - mid + 1
            } else {
                nums[k] = temp[l]
                l += 1
            }
            k += 1
        }
        
        print(nums[left...right], n)
        return n
    }
}
